package cn.zifangsky.linkedlist.questions;

import org.junit.Test;

import cn.zifangsky.linkedlist.SinglyNode;
import cn.zifangsky.linkedlist.SinglyNodeOperations;

/**
 * 如何将两个有序链表合并成一个新的有序链表？
 * @author zifangsky
 *
 */
public class Problem_010_MergeSortedList {
	
	/**
	 * 思路：递归依次比较大小
	 * @时间复杂度 O(n/2) = O(n)
	 * @param headNode
	 * @return
	 */
	public SinglyNode<Integer> MergeList(SinglyNode<Integer> headNode1,SinglyNode<Integer> headNode2){
		SinglyNode<Integer> result = null;
		
		if(headNode1 == null) return headNode2;
		if(headNode2 == null) return headNode1;
		
		if(headNode1.getData() <= headNode2.getData()){
			result = headNode1;
			result.setNext(MergeList(headNode1.getNext(),headNode2));
		}else{
			result = headNode2;
			result.setNext(MergeList(headNode1,headNode2.getNext()));
		}
		return (SinglyNode<Integer>) result;
	}
	
	@Test
	public void testMethods(){
		SinglyNode<Integer> a = new SinglyNode<Integer>(11);
		SinglyNode<Integer> b = new SinglyNode<Integer>(22);
		
		SinglyNode<Integer> currentA = a,currentB = b;
		for(int i=3;i<=8;i++){
			SinglyNode<Integer> tmpNode = new SinglyNode<Integer>(11 * i);
			
			if(i%2 == 0){
				currentB.setNext(tmpNode);
				currentB = tmpNode;
			}else{
				currentA.setNext(tmpNode);
				currentA = tmpNode;
			}

		}
		
		//遍历初始链表
		System.out.print("A: ");
		SinglyNodeOperations.print(a);
		System.out.print("B: ");
		SinglyNodeOperations.print(b);
		
		System.out.print("合并之后: ");
		SinglyNodeOperations.print(MergeList(a, b));
	}
	
}
